home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / iutil / delete_btree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-01-23  |  12.4 KB  |  455 lines
  1. # include    <stdio.h>
  2. # include    <btree.h>
  3. # include    <ingres.h>
  4. # include    <batch.h>
  5. # include    <sccs.h>
  6.  
  7. SCCSID(@(#)delete_btree.c    8.1    12/31/84)
  8.  
  9. /*    DELETE_BTREE -- BTree deletion routine
  10. **
  11. **    Deletes a tid from a leaf node and adjusts all values up the tree
  12. **
  13. **    Parameters :
  14. **        tree - BTree filename (I)
  15. **        lid - lid to be deleted (I)
  16. **
  17. **    Returns :
  18. **        > 0     success
  19. **        < 0     bad lid
  20. */
  21.  
  22. delete_btree(lid, level)
  23. long lid[];
  24. register int level;
  25.  
  26. {
  27.     register int        i, j;
  28.     struct locator        tid[MAXLID];
  29.     register int        save;
  30.     int            num[MAXLID];
  31.     int            del[MAXLID];
  32.     long            page[MAXLID + 1], t;
  33.     struct BTreeNode    temp;
  34.  
  35. #    ifdef xATR1
  36.     if(tTf(24,0))
  37.         printf("deleting lid %ld from tree ", lid);
  38. #    endif
  39.  
  40.     page[0] = RT;
  41.     for (i = 0; i < level; ++i)
  42.     {
  43.         if ((t = get_tid(page[i], lid[i], &tid[i])) < 0)
  44.             return(-1);
  45.         del[i] = 0;
  46.         num[i] = tid[i].page.nelmts; 
  47.         page[i+1] = t;
  48.     }
  49.  
  50.     del[level-1] = 1;
  51.     for (i = level - 2; i >= 0; --i)
  52.     {
  53.         if (num[i + 1] == 1 && del[i + 1] == 1)
  54.             del[i] = 1;
  55.     }
  56.  
  57.     for (i = 0; i < level; ++i)
  58.     {
  59.         if (del[i])
  60.         {
  61.             ++Repl_cnt[i];
  62.             for (j = i - 1; j >= 0; --j)
  63.                 Prev_lid[j] = lid[j];
  64.             /* remove tid from leaf */
  65.             if (tid[i].offset != tid[i].page.nelmts - 1)
  66.             {
  67.                 save = tid[i].page.node.leafnode.tid_loc[tid[i].offset];
  68.                 for (j = tid[i].offset; j < tid[i].page.nelmts; ++j)
  69.                 {
  70.                     tid[i].page.node.leafnode.tid_loc[j] =
  71.                         tid[i].page.node.leafnode.tid_loc[j + 1];
  72.                     tid[i].page.node.leafnode.back_ptr[tid[i].page.node.leafnode.tid_loc[j]] = j;
  73.                 }
  74.                 tid[i].page.node.leafnode.tid_loc[tid[i].page.nelmts - 1] = save;
  75.                 tid[i].page.node.leafnode.back_ptr[save] = tid[i].page.nelmts - 1;
  76.             }
  77.             --tid[i].page.nelmts;
  78.  
  79.             if (tid[i].page.nelmts != 0)
  80.             {
  81.                 write_node(tid[i].pageno, &tid[i].page);
  82.                 /* leaf is now empty as a result of deletion, decrement keys
  83.                 ** up tree */
  84.                 tracepath(page[i], &tid[i], -1);
  85.             }
  86.  
  87.             else if (tid[i].pageno != page[i])
  88.             {
  89.                 /* key/ptr pair corresponding to empty leaf must be removed */
  90.                 delete_key(page[i], &tid[i]);
  91.             }
  92.             else if (lid[i] == 1 && page[i] != RT)
  93.             {
  94.                 if (tid[i].page.prevtree)
  95.                 {
  96.                     get_node(tid[i].page.prevtree, &temp);
  97.                     temp.nexttree = tid[i].page.nexttree;
  98.                     write_node(tid[i].page.prevtree, &temp);
  99.                 }
  100.                 if (tid[i].page.nexttree)
  101.                 {
  102.                     get_node(tid[i].page.nexttree, &temp);
  103.                     temp.prevtree = tid[i].page.prevtree;
  104.                     write_node(tid[i].page.nexttree, &temp);
  105.                 }
  106.                 return_page(page[i]);
  107.             }
  108.             else
  109.                 write_node(page[i], &tid[i].page);
  110.         }
  111.     }
  112.     return(0);
  113. }
  114.  
  115. /*    Returns an empty page to the empty file space list.  Removes key/ptr
  116. **     pair corresponding to empty node from tree.  Combines and distributes
  117. **    pairs if a node has less than the minimum number of values.  Adjusts
  118. **    all values up the tree.
  119. **
  120. **    Parameters :
  121. **        tree - BTree filename (I)
  122. **        empty - empty node (I)
  123. */
  124.  
  125. delete_key(rootpage, empty)
  126.  
  127. long rootpage;
  128. register struct locator *empty;
  129. {
  130.     struct locator        prt, gprt, sibling;
  131.     register int        i;
  132.     struct BTreeNode    new, temp;
  133.     long            pkey, skey;
  134.     extern char        *Fileset;
  135.     char            replbatch[MAXNAME + 4];
  136.     FILE            *fp;
  137.     long            count, page;
  138.     TID            oldtid, newtid;
  139.  
  140.     /* find parent corresponding to empty node, and remove ptr/key pair
  141.     ** from parent */
  142.     prt.pageno = empty->page.parent;
  143.     parentkey(empty->pageno, &prt);
  144.     if (prt.offset != prt.page.nelmts - 1)
  145.     {
  146.         for (i = prt.offset; i < prt.page.nelmts; ++i)
  147.         {
  148.             prt.page.node.intnode.ptr[i] = 
  149.                 prt.page.node.intnode.ptr[i + 1];
  150.             prt.page.node.intnode.key[i] =
  151.                 prt.page.node.intnode.key[i + 1];
  152.         }
  153.     }
  154.     --prt.page.nelmts;
  155.  
  156.     if (empty->page.nodetype == 'L')
  157.     /* adjust previous and next fields of leaves */
  158.     {
  159.         if (empty->page.node.leafnode.nextleaf != 0)
  160.         {
  161.             get_node(empty->page.node.leafnode.nextleaf, &temp);
  162.             temp.node.leafnode.prevleaf = empty->page.node.leafnode.prevleaf;
  163.             write_node(empty->page.node.leafnode.nextleaf, &temp);
  164.         }
  165.         if (empty->page.node.leafnode.prevleaf != 0)
  166.         {
  167.             get_node(empty->page.node.leafnode.prevleaf, &temp);
  168.             temp.node.leafnode.nextleaf = empty->page.node.leafnode.nextleaf;
  169.             write_node(empty->page.node.leafnode.prevleaf, &temp);
  170.         }
  171.     }
  172.  
  173.     /* return empty node to empty file space */
  174.     return_page(empty->pageno);
  175.  
  176.     if (prt.page.nelmts >= (int) ((float) MAXPTRS / 2 + 0.5))
  177.     {
  178.         write_node(prt.pageno, &prt.page);
  179.         /* node still has proper number of elements, decrement key  
  180.         ** values up the tree */
  181.         tracepath(rootpage, &prt, -1);
  182.     }
  183.  
  184.     else if (prt.pageno == rootpage && prt.page.nelmts < 2)
  185.     /* root has only one child, a leaf; root becomes leaf node */
  186.     {
  187.         /* move leaf values into root; root's position always remains
  188.         ** the same */
  189.         get_node(prt.page.node.intnode.ptr[0], &new);
  190.         new.parent = prt.page.parent;
  191.         write_node(rootpage, &new);
  192.         return_page(prt.page.node.intnode.ptr[0]);
  193.         if (new.nodetype  == 'I')
  194.         {
  195.             for (i = 0; i < new.nelmts; ++i)
  196.             {
  197.                 get_node(new.node.intnode.ptr[i], &temp);
  198.                 temp.parent = rootpage;
  199.                 write_node(new.node.intnode.ptr[i], &temp);
  200.             }
  201.         }
  202.         else
  203.         {
  204.             /* btree tid is being changed, must be reflected in
  205.             ** secondary btree relation
  206.             */
  207.             concat(REPL_IN, Fileset, replbatch);
  208.             if ((fp = fopen(replbatch, "w")) == NULL)
  209.                 syserr("can't open replbatch in delete_btree");
  210.             count = 0;
  211.             page = 0l;
  212.             stuff_page(&newtid, &page);
  213.             stuff_page(&oldtid, &prt.page.node.intnode.ptr[0]);
  214.             for (i = 0; i < new.nelmts; ++i)
  215.             {
  216.                 oldtid.line_id = newtid.line_id = new.node.leafnode.tid_loc[i];
  217.                 if (fwrite(&oldtid, 1, LIDSIZE, fp) != LIDSIZE)
  218.                     syserr("write error in delete_btree");
  219.                 if (fwrite(&newtid, 1, LIDSIZE, fp) != LIDSIZE)
  220.                     syserr("write error in delete_btree");
  221.                 ++count;
  222.             }
  223.             fclose(fp);
  224.             repl_btree(replbatch, count);
  225.             unlink(replbatch);
  226.             unlink(ztack(REPL_OUT, Fileset));
  227.         }
  228.     }
  229.  
  230.     else if (prt.pageno != rootpage)
  231.     {
  232.         /* find the grandparent of the empty node */
  233.         gprt.pageno = prt.page.parent;
  234.         parentkey(prt.pageno, &gprt);
  235.         if (gprt.page.nelmts - 1 != gprt.offset)
  236.         {
  237.             /* determine the right sibling of the parent node */
  238.             sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset + 1];
  239.             get_node(sibling.pageno, &sibling.page);
  240.  
  241.             if (sibling.page.nelmts > MAXPTRS / 2 + 1)
  242.             /* distribute key/ptr pairs of parent and right sibling
  243.             ** between the two nodes (since there are sufficient
  244.             ** pairs to guarantee that both will have at the least
  245.             ** the minimum number of required children) */
  246.             {
  247.                 distribute(&prt, &sibling, &pkey, &skey);
  248.                 /* adjust key values in grandparent */
  249.                 gprt.page.node.intnode.key[gprt.offset] = pkey;
  250.                 gprt.page.node.intnode.key[gprt.offset + 1] = skey;
  251.                 write_node(gprt.pageno, &gprt.page);
  252.                 tracepath(rootpage, &gprt, -1);
  253.                 return;
  254.             }
  255.         }
  256.         if (gprt.offset != 0)
  257.         {
  258.             /* determine the left sibling of the parent node */
  259.             sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset - 1];
  260.             get_node(sibling.pageno, &sibling.page);
  261.  
  262.             if (sibling.page.nelmts > MAXPTRS / 2 + 1)
  263.             /* distribute key/ptr pairs of parent and left sibling
  264.             ** between the two nodes */
  265.             {
  266.                 distribute(&sibling, &prt, &skey, &pkey);
  267.                 gprt.page.node.intnode.key[gprt.offset - 1] = skey;
  268.                 gprt.page.node.intnode.key[gprt.offset] = pkey;
  269.                 write_node(gprt.pageno, &gprt.page);
  270.                 tracepath(rootpage, &gprt, -1);
  271.                 return;
  272.             }
  273.         }
  274.  
  275.         if (gprt.page.nelmts - 1 != gprt.offset)
  276.         /* combine parent node with its right sibling */
  277.         {
  278.             sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset + 1];
  279.             get_node(sibling.pageno, &sibling.page);
  280.             combine(&prt, &sibling);
  281.         }
  282.         else
  283.         /* combine parent node with its left sibling */
  284.         {
  285.             sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset - 1];
  286.             get_node(sibling.pageno, &sibling.page);
  287.             combine(&sibling, &prt);
  288.             /* grandparent should point to newly combined block,
  289.             ** the left sibling */
  290.             --gprt.offset;
  291.         }
  292.  
  293.         get_node(gprt.page.node.intnode.ptr[gprt.offset], &new);
  294.         if (gprt.pageno == rootpage && gprt.page.nelmts == 2)
  295.         /* root has only one child, reduce B-Tree level */
  296.         {
  297.             /* only child becomes root */
  298.             new.parent = gprt.page.parent;
  299.             write_node(rootpage, &new);
  300.  
  301.             /* make sure "new's" children's parent is the root */
  302.             for (i = 0; i < new.nelmts; ++i)
  303.             {
  304.                 get_node(new.node.intnode.ptr[i], &temp);
  305.                 temp.parent = rootpage;
  306.                 write_node(new.node.intnode.ptr[i], &temp);
  307.             }
  308.             /* both of root's children empty */
  309.             return_page(gprt.page.node.intnode.ptr[gprt.offset + 1]);
  310.             return_page(gprt.page.node.intnode.ptr[gprt.offset]);
  311.         }
  312.  
  313.         else
  314.         {
  315.             /* adjust key value in grandparent node */
  316.             pkey = 0;
  317.             for (i = 0; i < new.nelmts; ++i)
  318.                 pkey += new.node.intnode.key[i];
  319.             gprt.page.node.intnode.key[gprt.offset] = pkey;
  320.             write_node(gprt.pageno, &gprt.page);
  321.  
  322.             /* remove ptr/key pair corresponding to empty node */
  323.             gprt.pageno = gprt.page.node.intnode.ptr[gprt.offset + 1];
  324.             get_node(gprt.pageno, &gprt.page);
  325.             delete_key(rootpage, &gprt);
  326.         }
  327.     
  328.     }
  329. }
  330.  
  331. /*    Divides key/ptr pairs between the left and right nodes, so both will
  332. **    have the proper number of elements.
  333. **
  334. **    Parameters :
  335. **        tree - BTree filename (I)
  336. **        left - left node (I, O)
  337. **        right - "left's" right sibling (I, O)
  338. **        lkey - key value of the parent of left node (O)
  339. **        rkey - key value of the parent of right node (O)
  340. */
  341.  
  342. distribute(left, right, lkey, rkey)
  343.  
  344. register struct locator *left, *right;
  345. int *lkey, *rkey;
  346. {
  347.     register int        i, move;
  348.     struct BTreeNode    temp;
  349.  
  350.     if (right->page.nelmts > left->page.nelmts)
  351.     /* move elements from the right node to the left node */
  352.     {
  353.         move = MAXPTRS / 2 - left->page.nelmts;
  354.  
  355.         for (i = 1; i <= move; ++i)
  356.         /* move first part of right node into the end of the left node */
  357.         {
  358.             left->page.node.intnode.ptr[i + left->page.nelmts] =
  359.                 right->page.node.intnode.ptr[i - 1];
  360.             left->page.node.intnode.key[i + left->page.nelmts] =
  361.                 right->page.node.intnode.key[i - 1];
  362.             /* adjust parents of children whose parents have been
  363.             ** moved */
  364.             get_node(left->page.node.intnode.ptr[i + left->page.nelmts], &temp);
  365.             temp.parent = left->pageno;
  366.             write_node(left->page.node.intnode.ptr[i + left->page.nelmts], &temp);
  367.         }
  368.         left->page.nelmts += move;
  369.  
  370.         for (i = move; i < right->page.nelmts; ++i)
  371.         /* flush right node values to the left */
  372.         {
  373.             right->page.node.intnode.ptr[i - move] =
  374.                 right->page.node.intnode.ptr[i];
  375.             right->page.node.intnode.key[i - move] =
  376.                 right->page.node.intnode.key[i];
  377.         }
  378.         right->page.nelmts -= move;
  379.     }
  380.  
  381.     else
  382.     /*  move left node values to the right node */
  383.     {
  384.         move = MAXPTRS / 2 - right->page.nelmts + 1;
  385.  
  386.         /* move right node values to the right to make room for left
  387.         ** node values */
  388.         for (i = right->page.nelmts - 1; i >= 0; --i)
  389.         {
  390.             right->page.node.intnode.ptr[i + move] =
  391.                 right->page.node.intnode.ptr[i];
  392.             right->page.node.intnode.key[i + move] =
  393.                 right->page.node.intnode.key[i];
  394.         }
  395.  
  396.         /* move latter part of left node into the now free space at the
  397.         ** beginning of the right node */
  398.         for (i = 0; i < move; ++i)
  399.         {
  400.             right->page.node.intnode.ptr[i] = 
  401.                 left->page.node.intnode.ptr[left->page.nelmts - move + i];
  402.             right->page.node.intnode.key[i] =
  403.                 left->page.node.intnode.key[left->page.nelmts - move + i];
  404.             /* adjust parents of children whose parents have been
  405.             ** moved */
  406.             get_node(right->page.node.intnode.ptr[i], &temp);
  407.             temp.parent = right->pageno;
  408.             write_node(right->page.node.intnode.ptr[i], &temp);
  409.         }
  410.         left->page.nelmts -= move;
  411.         right->page.nelmts += move;
  412.     }
  413.  
  414.     /* calculate key values for parents of the left and right nodes */
  415.     *lkey = 0;
  416.     for (i = 0; i < left->page.nelmts; ++i)
  417.         *lkey += left->page.node.intnode.key[i];
  418.     *rkey = 0;
  419.     for (i = 0; i < right->page.nelmts; ++i)
  420.         *rkey += right->page.node.intnode.key[i];
  421.     write_node(left->pageno, &left->page);
  422.     write_node(right->pageno, &right->page);
  423. }
  424.  
  425. /*    Combines left and right nodes together to form one node.
  426. **
  427. **    Parameters :
  428. **        tree - BTree filename (I)
  429. **        left - left node (I, O)
  430. **        right - "left's" right sibling (I)
  431. */
  432.  
  433. combine(left, right)
  434.  
  435. register struct locator *left, *right;
  436. {
  437.     register int        i;
  438.     struct BTreeNode    temp;
  439.  
  440.     /* move all ptr/key values in the right node to the end of the left node */
  441.     for (i = 0; i < right->page.nelmts; ++i)
  442.     {
  443.         left->page.node.intnode.ptr[left->page.nelmts + i] =
  444.             right->page.node.intnode.ptr[i];
  445.         left->page.node.intnode.key[left->page.nelmts + i] =
  446.             right->page.node.intnode.key[i];
  447.         /* adjust parents of children whose parents have been moved */
  448.         get_node(left->page.node.intnode.ptr[left->page.nelmts + i], &temp);
  449.         temp.parent = left->pageno;
  450.         write_node(left->page.node.intnode.ptr[left->page.nelmts + i], &temp);
  451.     }
  452.     left->page.nelmts += right->page.nelmts;
  453.     write_node(left->pageno, &left->page);
  454. }
  455.